package org.zhangyp.n03algorithm.n03Sort;

import java.util.Arrays;

/**
 * 插入&希尔&归并
 *
 * @author ypzhang
 * @since 2024/12/25
 */
public class ASort {

    private static Object[] temp; // 归并排序的临时数组

    /**
     * 插入排序
     * 理解为打扑克时抓牌的过程
     * 分为有序区间和无序区间，从无序的列表中拿出一个数插入到有序的列表中
     *
     * @param data
     */
    public static <T extends Number> void insertSort(T[] data) {
        for (int i = 1; i < data.length; i++) {
            T val = data[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (val.doubleValue() < data[j].doubleValue()) {
                    //比该数小，应该插入到该数的前面，将该数往后移动一个位置
                    data[j + 1] = data[j];
                    // 如果j一直到0都比它小，j会变成-1，也是该插入数据的前一个位置
                } else {
                    // 证明已经到了该插入数据的前一个位置
                    break;
                }
            }
            data[j + 1] = val;
        }
    }


    /**
     * 希尔排序
     * 执行排序前尽量将数据调整为有序的，从而减少插入时的遍历次数
     *
     * @param data
     */
    public static <T extends Number> void shellSort(T[] data) {
        int step = data.length / 2;
        while (step > 1) {
            insertSort(data, step);
            step = step / 2;
        }
        insertSort(data, 1);
    }

    /**
     * 带步长的插入排序
     *
     * @param data
     * @param step
     */
    private static <T extends Number> void insertSort(T[] data, int step) {
        int len = data.length;
        for (int i = 1; i < len / step; i++) {
            T val = data[i * step];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (val.doubleValue() < data[j * step].doubleValue()) {
                    //比该数小，应该插入到该数的前面，将该数往后移动一个位置
                    data[(j + 1) * step] = data[j * step];
                    // 如果j一直到0都比它小，j会变成-1，也是该插入数据的前一个位置
                } else {
                    // 证明已经到了该插入数据的前一个位置
                    break;
                }
            }
            data[(j + 1) * step] = val;
        }
    }

    /**
     * 归并排序
     *
     * @param data
     */
    public static <T extends Number> void mergeSort(T[] data) {
        System.out.println("length = " + data.length + " data last = " + data[data.length - 1]);
        temp = new Object[data.length];
        mergeSort(data, 0, data.length - 1);
        // 释放临时数组空间
        temp = null;
    }

    public static <T extends Number> void mergeSort(T[] data, int start, int end) {
        if (start < end) {

            int mid = start + (end - start) / 2;
            // 分
            mergeSort(data, start, mid);
            mergeSort(data, mid + 1, end);

            // 合
            int tempIndex = start;
            // 左右两边拿出来比较，生成新的有序数组
            int leftIndex = start; //左边当前数的指针
            int rightIndex = mid + 1; // 右边从左到右当前数的指针
            while (leftIndex <= mid && rightIndex <= end) {
                if (data[leftIndex].doubleValue() <= data[rightIndex].doubleValue()) {
                    temp[tempIndex++] = data[leftIndex++];
                } else {
                    temp[tempIndex++] = data[rightIndex++];
                }
            }
            // 左右两边都可能剩下很长一串有序的数
            while (leftIndex <= mid) {
                temp[tempIndex++] = data[leftIndex++];
            }
            while (rightIndex <= end) {
                temp[tempIndex++] = data[rightIndex++];
            }
            for (int i = start; i <= end; i++) {
                data[i] = (T) temp[i];
            }
        }
    }

    public static void main(String[] args) {
        double[] data = {9, 3, 4, 6, 1, 2, 7, 5, 0, 8};
        //mergeSort(data);
        System.out.println(Arrays.toString(data));
    }

}
